package com.sheng.leetcode.year2022.month08.day30;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/08/30
 *
 * 998. 最大二叉树 II
 *
 * 最大树 定义：一棵树，并满足：其中每个节点的值都大于其子树中的任何其他值。
 * 给你最大树的根节点 root 和一个整数 val 。
 * 就像 之前的问题 那样，给定的树是利用 Construct(a) 例程从列表 a（root = Construct(a)）递归地构建的：
 * 如果 a 为空，返回 null 。
 * 否则，令 a[i] 作为 a 的最大元素。创建一个值为 a[i] 的根节点 root 。
 * root 的左子树将被构建为 Construct([a[0], a[1], ..., a[i - 1]]) 。
 * root 的右子树将被构建为 Construct([a[i + 1], a[i + 2], ..., a[a.length - 1]]) 。
 * 返回 root 。
 * 请注意，题目没有直接给出 a ，只是给出一个根节点 root = Construct(a) 。
 * 假设 b 是 a 的副本，并在末尾附加值 val。题目数据保证 b 中的值互不相同。
 * 返回 Construct(b) 。
 *
 * 示例 1：
 * 输入：root = [4,1,3,null,null,2], val = 5
 * 输出：[5,4,null,1,3,null,null,2]
 * 解释：a = [1,4,2,3], b = [1,4,2,3,5]
 *
 * 示例 2：
 * 输入：root = [5,2,4,null,1], val = 3
 * 输出：[5,2,4,null,1,null,3]
 * 解释：a = [2,1,5,4], b = [2,1,5,4,3]
 *
 * 示例 3：
 * 输入：root = [5,2,3,null,1], val = 4
 * 输出：[5,2,4,null,1,3]
 * 解释：a = [2,1,5,3], b = [2,1,5,3,4]
 *
 * 提示：
 *
 * 树中节点数目在范围 [1, 100] 内
 * 1 <= Node.val <= 100
 * 树中的所有值 互不相同
 * 1 <= val <= 100
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/maximum-binary-tree-ii
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class LeetCode0998 {

    @Test
    public void test01() {
//        TreeNode root = new TreeNode(4);
//        TreeNode right = new TreeNode(3);
//        right.left = new TreeNode(2);
//        root.left = new TreeNode(1);
//        root.right = right;
//        int val = 5;

//        TreeNode root = new TreeNode(5);
//        TreeNode left = new TreeNode(2);
//        left.right = new TreeNode(1);
//        root.left = left;
//        root.right = new TreeNode(4);
//        int val = 3;

//        TreeNode root = new TreeNode(5);
//        TreeNode left = new TreeNode(2);
//        left.right = new TreeNode(1);
//        root.left = left;
//        root.right = new TreeNode(3);
//        int val = 4;

        TreeNode root = new TreeNode(6);
        root.left = new TreeNode(3);
        root.right = new TreeNode(4);
        int val = 2;
        TreeNode treeNode = new Solution().insertIntoMaxTree(root, val);
        System.out.println(treeNode);
    }
}

class Solution {
    public TreeNode insertIntoMaxTree(TreeNode root, int val) {
        // 如果当前结点为空
        if (root == null) {
            return new TreeNode(val);
        }
        // 如果val的值大于当前结点的值，则创建一个新的结点，将老结点作为新结点的左结点
        if (val > root.val) {
            TreeNode treeNode = new TreeNode(val);
            treeNode.left = root;
            return treeNode;
        }
        // 如果val的值小余当前结点的值，则将val值对当前结点的右结点进行递归
        root.right = insertIntoMaxTree(root.right, val);
        return root;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
